import collections
# class Solution(object):
#     def canPartition(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: bool
#         """
#         total = sum(nums)
#         n = len(nums)
#         if total % 2 == 1:
#             return False
#         total = total // 2
#         DP = [[False] * (total + 1) for _ in range(n)]
#         DP[0][0] = True
#         if nums[0] > total:
#             return False
#         DP[0][nums[0]] = True
#         for i in range(1, n):
#             for j in range(total + 1):
#                 if DP[i - 1][j]:
#                     DP[i][j] = True
#                     if j + nums[i] == total:
#                         return True
#                     else:
#                         if j + nums[i] < total:
#                             DP[i][j + nums[i]] = True
#
#         return False
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        total = sum(nums)
        n = len(nums)
        if total % 2 == 1:
            return False
        total = total // 2
        sum_dict = collections.defaultdict(bool)
        sum_dict[0] = True
        for item in nums:
            new_dict = collections.defaultdict(bool)
            for key in sum_dict:
                new_dict[key] = True
                val = key + item
                if val == total:
                    return True
                else:
                    if val < total:
                        new_dict[val] = True
            sum_dict = new_dict
        return False


data = Solution()
nums = [1,2,5]
print(data.canPartition(nums))
nums = [14,9,8,4,3,2]
print(data.canPartition(nums))
nums = [100]
print(data.canPartition(nums))